package LeetCode热题HOT100;

import 剑指offer.ListNode;

public class p234回文链表 {
    public boolean isPalindrome(ListNode head) {
        //回文链表：顺序遍历和逆序遍历得到的链表节点值一样
        //思路：使用快慢指针，快指针快一步，当快指针为空，或快指针.next为空，此时慢指针在链表的中间节点
        //     再翻转后一部分的链表，从头到中间 和 从尾到中间，判断节点值是否相等，最后判断是否为回文链表
        if (head.next==null) {
            return true;//一个节点也是回文链表
        }
        ListNode fast=head;
        ListNode slow=head;

        //1.找到slow指向的链表中间节点
        while (fast!=null && fast.next!=null) {
            fast=fast.next.next;
            slow=slow.next;
        }

        //2.翻转 中间节点到尾节点
        ListNode cur=slow.next;
        while (cur!=null) {
            ListNode curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }

        //3.从头到中间 和 从尾到中间，判断节点值是否相等，最后判断是否为回文链表
        while (head!=slow) {
            //节点个数为奇数时，头指针和尾指针相遇，则是回文链表
            if (head.val != slow.val) {
                return false;
            }

            if (head.next==slow) {
                //节点个数为偶数时，头指针.next==尾指针，则是回文链表
                return true;
            }else {
                head=head.next;
                slow=slow.next;
            }
        }

        return true;
    }
}
